import scala.{Some => _, None => _, Option => _, List => _, Iterable => _}


// the "dual" of Iterator
trait Builder[Container[_], El] {
  def +=(el: El): Unit
  def finalise(): Container[El]
  
  final def using(op: this.type => Unit): Container[El] = {op(this); finalise()}
}

trait Buildable[Container[_]] {
  def builder[T]: Builder[Container, T]
  
  final def fromIterator[El, NewEl](elems: Iterator[El])(op: Builder[Container, NewEl] => El => Unit): Container[NewEl] 
    = builder.using{ b => elems.foreach(op(b)) }
}

trait Iterator[+El] {
  def next(): El
  def hasNext: Boolean
  
  def foreach(op: El => Unit): Unit = while(hasNext) op(next())
}

trait Iterable[+El] {
  type Container[+X] <: Iterable[X]
  
  def isEmpty: Boolean
  def elements: Iterator[El]

  final def map[NewEl](f: El => NewEl)(implicit b: Buildable[Container]): Container[NewEl] = mapTo[NewEl, Container](f)
  final def filter(p: El => Boolean)(implicit b: Buildable[Container]): Container[El] = filterTo[Container](p)
  final def flatMap[NewEl](f: El => Iterable[NewEl])(implicit b: Buildable[Container]): Container[NewEl] = flatMapTo[NewEl, Container](f)

  final def mapTo[NewEl, NewContainer[_]](f: El => NewEl)(implicit b: Buildable[NewContainer]): NewContainer[NewEl] = 
    b.fromIterator(elements){ builder => el => builder += f(el) }
    
  final def filterTo[NewContainer[+X]](p: El => Boolean)(implicit b: Buildable[NewContainer]): NewContainer[El] = 
    b.fromIterator(elements){ builder => el => if(p(el)) builder += el}

  // doesn't make sense to have f determine the resulting container
  final def flatMapTo[NewEl, NewContainer[X]](f: El => Iterable[NewEl])(implicit b: Buildable[NewContainer]): NewContainer[NewEl] = 
    b.fromIterator(elements){ builder => el =>
      f(el).elements.foreach{ el => builder += el }
    }
}


trait Lists {
  sealed abstract class List[+t] extends Iterable[t] {
    type Container[+X] = List[X]
    
    def head: t
    def tail: List[t]
    def elements: Iterator[t] = new Iterator[t] {
      var these = List.this
      def hasNext: Boolean = !these.isEmpty
      def next: t =
        if (!hasNext)
          throw new NoSuchElementException("next on empty Iterator")
        else {
          val result = these.head; these = these.tail; result
        }
    }
  }
  
  final case class ::[b](hd: b, private[Lists] var tl: List[b]) extends List[b] {
    def head = hd
    def tail = tl
    override def isEmpty: boolean = false
  }
  
  final case class Nil extends List[Nothing] {
    def isEmpty = true
    def head = throw new NoSuchElementException("head of empty list")
    def tail = throw new NoSuchElementException("tail of empty list")
  }

  class ListBuffer[A] {
    private var start: List[A] = Nil()
    private var last: ::[A] = _
    private var exported: boolean = false

    /** Appends a single element to this buffer.
     *
     *  @param x  the element to append.
     */
    final def += (x: A): unit = {
      if (exported) copy
      if (start.isEmpty) {
        last = new Lists.this.::(x, Nil())
        start = last
      } else {
        val last1 = last
        last = new Lists.this.:: (x, null)
        last1.tl = last
      }
    }

    /** Converts this buffer to a list
     */
    final def toList: List[A] = {
      exported = !start.isEmpty
      start
    }
    
    /** Clears the buffer contents.
     */
    final def clear: unit = {
      start = Nil()
      exported = false
    }

    /** Copy contents of this buffer */
    private def copy = {
      var cursor = start
      val limit = last.tail
      clear
      while (cursor ne limit) {
        this += cursor.head
        cursor = cursor.tail
      }
    }
  }
  
  implicit object ListIsBuildable extends Buildable[List] {
    def builder[El]: Builder[List, El] = new ListBuffer[El] with Builder[List, El] {
      def finalise(): List[El] = toList
    }
  }

  def sequence[C[+x] <: Iterable[x], A[+x] <: Iterable[x], T](xs: C[A[T]])(implicit bc: Buildable[C], ba: Buildable[A]): A[C[T]] = {
    val builder: Builder[C, T] = bc.builder[T]
    val res: Builder[A, C[T]] = ba.builder[C[T]]
    
    var fail = false
	xs.elements.foreach{ x: A[T] =>  if(!(fail || x.isEmpty)) x.elements.foreach{ e: T => builder += e} else fail=true  }
    if(!fail) res += builder.finalise()
    
    res.finalise()
  }   
}

trait Options {
  sealed abstract class Option[+A] extends Iterable[A] {
    type Container[+X] = Option[X]
    
    def get: A
    
    def elements: Iterator[A] = new Iterator[A] {
      var _hasNext = !isEmpty
      def hasNext: Boolean = _hasNext
      def next: A =
        if (!hasNext)
          throw new NoSuchElementException("next on empty Iterator")
        else {
          _hasNext = false
          get
        }
    }
  }

  final case class Some[A](x: A) extends Option[A] {
    def isEmpty = false
    def get = x
  }

  final case class None[A] extends Option[A] {
    def isEmpty = true
    def get = throw new NoSuchElementException("None.get")
  }
  
  implicit object OptionIsBuildable extends Buildable[Option] {
    def builder[El]: Builder[Option, El] = new Builder[Option, El] {
      var res: Option[El] = None()
      def +=(el: El) = if(res.isEmpty) res = Some(el) else throw new UnsupportedOperationException("An Option holds max 1 element")
      def finalise(): Option[El] = res
    }
  }  
}

object testSequence extends Options with Lists with Application {
   println(sequence[List, Option, Int](::(Some(10), ::(Some(2), Nil()))))
   println(sequence[List, Option, Int](::(Some(10), ::(None, Nil()))))   
}

object TestOptions extends Options with Lists {
  //::(Some(10), ::(None(), Nil())).flatMap()
}

trait TestCommon { 
  val Size = 200
  val N = 1000000

  val times2 = {x: Int => x * 2}
  
  def test: Long
}

object testListsNew extends Lists with TestCommon{
  var ints: List[Int] = Nil()
  
  for(i <- 1 to Size)
    ints = new ::(i, ints)

  def test = {
    val start = System.currentTimeMillis
  
    for(i <- 1 to N) {
      ints.map(times2)
    }

    System.currentTimeMillis-start
  }
}


object testListsOriginal extends TestCommon {
  var ints: List[Int] = Nil
  
  for(i <- 1 to Size)
    ints = new ::(i, ints)

  def test = {
    val start = System.currentTimeMillis
  
    for(i <- 1 to N) {
      ints.map(times2)
    }

    System.currentTimeMillis-start
  }
}

object testLists extends Application {
  val n: Double = testListsNew.test
  val o: Double = testListsOriginal.test
  println("new: "+ n +" original: "+ o +" ratio: "+ (n/o) )
}

trait BoundedMonads {
trait Iterable[T <: Bound[T], Bound[_]] {
  type Container[x <: Bound[x]]
  
  def map[S <: Bound[S]](f: T => S): Container[S] 
  def flatMap[S <: Bound[S]](f: T => Iterable[S, Bound]): Container[S] 
  def filter(p: T => Boolean): Container[T]
}

trait OrderedSet[T <: Ordered[T]] extends Iterable[T, Ordered] {
  type Container[x <: Ordered[x]] = OrderedSet[x]
}
}